package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

/**
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xoh1zg/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author waxijiang
 */
public class MaxDepth {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println("自顶向下的方法:"+maxDepthTopToDown(root, 0));
        System.out.println("自底向上的方法:"+maxDepthDownToTop(root));
    }


    /**
     * 自顶向下求解
     * @param root 根节点
     * @param depth 父节点深度
     * @return 树的最大深度
     */
    public static int maxDepthTopToDown(TreeNode root, int depth){
        if (root == null) {
            return depth;
        }

        int left = maxDepthTopToDown(root.left, depth + 1);
        int right = maxDepthTopToDown(root.right, depth + 1);
        return Math.max(left, right);
    }

    public static int maxDepthDownToTop(TreeNode root){
        if (root == null){
            return 0;
        }

        return Math.max(maxDepthDownToTop(root.left), maxDepthDownToTop(root.right)) + 1;
    }
}
